package item06;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Lv Jing
 * @date 2018年07月11日 23:52
 */
public class LinkedListTest {

    /*
    题目：从尾到头打印链表。要求不能改变链表结构
    从尾到头打印链表，但是我们遍历时是从头到尾遍历的，相当于先遍历的后打印，这很像栈的操作，所以可以使用一个栈来实现。
    或者使用递归，也是类似于栈，先打印下一个节点才能打印本节点，最后就是，最先打印尾节点，但是这种写法在链表很长时，
    容易造成递归深度过程，栈深度多大造成溢出。
    注意：题目为了便于结合测试用例，把打印改成传值到List
     */

    class ListNode {
        int value;
        ListNode next;

        ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }

    private List<Integer> invertPrintList(ListNode head) {
        if (head == null) {
            return null;
        }
        // 使用java提供的栈结构
        Stack<Integer> stack = new Stack<>();
        // 先遍历到的入栈
        stack.push(head.value);
        while (head.next != null) {
            head = head.next;
            stack.push(head.value);
        }
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    /**
     * 错误输入，输入null
     */
    @Test
    public void test01() {
        Assert.assertNull(invertPrintList(null));
    }

    /**
     * 输入的链表只有一个节点
     */
    @Test
    public void test02() {
        ListNode head = new ListNode(666, null);
        Assert.assertEquals(new Integer[]{666}, invertPrintList(head).toArray());
    }

    /**
     * 正常情况
     */
    @Test
    public void test03() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
        Assert.assertEquals(new Integer[]{4, 3, 2, 1}, invertPrintList(head).toArray());
    }
}
